//43. 字符串相乘
//中等
//相关标签
//premium lock icon
//相关企业
//给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
//
//注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
class Solution {
public:
    void MulItem(string& t, string& n, char c)
    {
        int i = 0, sign = 0;
        int mul = 0;
        while (i < n.size())
        {
            mul = (n[i] - '0') * (c - '0') + sign;
            if (mul >= 10)
            {
                sign = mul / 10;
                mul %= 10;
            }
            else sign = 0;
            t.push_back(mul + '0');
            i++;
        }
        if (sign > 0) t.push_back(sign + '0');
    }
    // 相加求和
    int AddItem(int a, int b, int& sign)
    {
        int sum = 0;
        sum = a + b + sign;
        if (sum >= 10)
        {
            sum -= 10;
            sign = 1;
        }
        else sign = 0;
        return sum;
    }
    // 错位相加, i用于控制错几位相加
    void MoveAdd(string& r, string& t, int i)
    {
        int j = 0;
        int sign = 0;
        while (i < r.size() && j < t.size())
        {
            r[i] = AddItem(r[i] - '0', t[j] - '0', sign) + '0';
            i++;
            j++;
        }
        while (i < r.size() && sign)
        {
            r[i] = AddItem(r[i] - '0', 0, sign) + '0';
            i++;
        }
        while (j < t.size())
        {
            int v = AddItem(0, t[j] - '0', sign);
            r.push_back(v + '0');
            j++;
        }
        if (sign) r.push_back(sign + '0');
    }
    string multiply(string num1, string num2) {
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());
        string tmp, res;
        for (int i = 0; i < num2.size(); i++)
        {
            // 将num2逐位乘以num1, 并将当次结果存储到tmp中
            MulItem(tmp, num1, num2[i]);
            // 将tmp中结果错位相加到res
            MoveAdd(res, tmp, i);
            // 完成当前位的计算，清空tmp准备继续下一位数据计算
            tmp.clear();
        }
        // 消除前导零
        while (res.size() != 1 && res.back() == '0') res.pop_back();
        // 翻转恢复数据
        reverse(res.begin(), res.end());
        return res;
    }
};